{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# 1. Programming a Chess Player" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "CS371: Introduction to Cognitive Science \n", "Bryn Mawr College \n", "Department of Computer Science \n", "Professor Blank, Fall 2016" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Goals**:\n", "\n", "* explore the idea that a computer could \"think\"\n", "* explore symbolic computation\n", "* write a program to play Chess\n", "\n", "In this notebook we will begin to explore *symbolic computation* by writing a program to play Chess. Perhaps you don't know how to play Chess... no problem! You don't really need to know much, but a primer on Chess may be useful. Here are some links that might be useful:\n", "\n", "**Getting Started with Chess**:\n", "\n", "* http://www.chesscorner.com/tutorial/learn.htm\n", "* https://www.chesscademy.com/\n", "* http://learningchess.net/us/index\n", "* https://www.chess.com/learn-how-to-play-chess\n", "\n", "For these experiments, we will use the `python-chess` library. In this notebook, we will define three different sample players. We explore them in some depth here to attempt to understand how each plays chess.\n", "\n", "**python-chess Reference**:\n", "\n", "* https://python-chess.readthedocs.io/en/v0.15.0/core.html" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 1.1 Game Play" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The first thing we need to do is import the chess library:" ] }, { "cell_type": "code", "execution_count": 1, "metadata": { "collapsed": true }, "outputs": [], "source": [ "import chess" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We will use the chess library in the following manner:\n", "\n", "1. Create a chess.Board instance\n", "1. The chess.Board instance automatically generates all possible moves for the current player\n", "1. Current player picks a move\n", "1. Go to step #2 and repeat until win, lose, or draw\n", "\n", "That's it! Thus we have reduced the playing a valid game of chess into simply selecting a move at each turn. To play a good game of chess, you will want to pick \"the best move\" at each turn. \n", "\n", "A player will be a function that takes a board instance as a argument, and returns a move encoded as a string in Universal Chess Interface format:\n", "\n", "```python\n", "def player(board):\n", " ### \"Thinking\" happens here\n", " return move_code\n", "```" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We'll explain this fully below." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 1.2 The Board class" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The Board class keeps track of whose turn it is, possible moves, and a history of all past moves. This class can undo and redo moves, and keeps track of repeating states. \n", "\n", "First, we create a board instance:" ] }, { "cell_type": "code", "execution_count": 2, "metadata": { "collapsed": false }, "outputs": [], "source": [ "board = chess.Board()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The `board.turn` value is a boolean indicating whose turn it is. The values are either True for white or False for black." ] }, { "cell_type": "code", "execution_count": 3, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "board.turn" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "As seen above, the game always begins with white's turn. If you forget which is True, you can ask the chess module:" ] }, { "cell_type": "code", "execution_count": 4, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "board.turn == chess.WHITE" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The chess.Board class is responsible for generating all possible moves, whose turn it is, keeping track of the placement of all pieces, and making each move. The chess.Board represents a two-dimensional 8 x 8 array. However, the internal representation is optimized for speedy operations.\n", "\n", "Here is a visual representation of a chess.Board:" ] }, { "cell_type": "code", "execution_count": 5, "metadata": { "collapsed": false }, "outputs": [ { "data": { "image/svg+xml": [ "" ], "text/plain": [ "Board('rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1')" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "board" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "You can also get an ASCII board representation (text-only) by converting the board into a string:" ] }, { "cell_type": "code", "execution_count": 6, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "r n b q k b n r\n", "p p p p p p p p\n", ". . . . . . . .\n", ". . . . . . . .\n", ". . . . . . . .\n", ". . . . . . . .\n", "P P P P P P P P\n", "R N B Q K B N R\n" ] } ], "source": [ "print(str(board))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The string representation of the board shows the character representation for each piece. Specifically:\n", "\n", "Piece | White | Black\n", "------|-------|--------\n", "Pawn | P | p\n", "Rook | R | r\n", "Knight | N | n\n", "Bishop | B | b\n", "Queen | Q | q\n", "King | K | k\n", " " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "For our uses, you don't really need to know how each piece moves. We discuss game strategy, though, shortly.\n", "\n", "The 2-dimensional board is laid out so that each position is indicated by a column letter and row number. However, the internal representation is sequential. Say that we wanted to see what was at location 'c1' we could use:" ] }, { "cell_type": "code", "execution_count": 7, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "2" ] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" } ], "source": [ "chess.C1" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "to get the internal location of the column/row, and then use:" ] }, { "cell_type": "code", "execution_count": 8, "metadata": { "collapsed": false }, "outputs": [ { "data": { "image/svg+xml": [ "" ], "text/plain": [ "Piece.from_symbol('B')" ] }, "execution_count": 8, "metadata": {}, "output_type": "execute_result" } ], "source": [ "board.piece_at(chess.C1)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Or shown as a character:" ] }, { "cell_type": "code", "execution_count": 9, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "'B'" ] }, "execution_count": 9, "metadata": {}, "output_type": "execute_result" } ], "source": [ "str(board.piece_at(chess.C1))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Indeed, there is a white bishop at 'c1'." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 1.3 Making Moves" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "At this point, we can as the board instance to generate all of the possible, legal moves:" ] }, { "cell_type": "code", "execution_count": 10, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "[Move.from_uci('b1a3'),\n", " Move.from_uci('b1c3'),\n", " Move.from_uci('g1f3'),\n", " Move.from_uci('g1h3'),\n", " Move.from_uci('a2a3'),\n", " Move.from_uci('b2b3'),\n", " Move.from_uci('c2c3'),\n", " Move.from_uci('d2d3'),\n", " Move.from_uci('e2e3'),\n", " Move.from_uci('f2f3'),\n", " Move.from_uci('g2g3'),\n", " Move.from_uci('h2h3'),\n", " Move.from_uci('a2a4'),\n", " Move.from_uci('b2b4'),\n", " Move.from_uci('c2c4'),\n", " Move.from_uci('d2d4'),\n", " Move.from_uci('e2e4'),\n", " Move.from_uci('f2f4'),\n", " Move.from_uci('g2g4'),\n", " Move.from_uci('h2h4')]" ] }, "execution_count": 10, "metadata": {}, "output_type": "execute_result" } ], "source": [ "list(board.legal_moves)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Python Note**: `board.legal_moves` looks like a normal list of items. But it is really a property that gets lazily generated on the fly. We force it to be a list by wrapping `list()` around it.\n", "\n", "We can get the first move (index zero):" ] }, { "cell_type": "code", "execution_count": 11, "metadata": { "collapsed": false }, "outputs": [], "source": [ "move = list(board.legal_moves)[0]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 1.3.1 Universal Chess Interface" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The Universal Chess Interface (or uci) is a representation for describing a move from one cell to another (and perhaps additional information as well). We explore the first move:" ] }, { "cell_type": "code", "execution_count": 12, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "Move.from_uci('b1a3')" ] }, "execution_count": 12, "metadata": {}, "output_type": "execute_result" } ], "source": [ "move" ] }, { "cell_type": "code", "execution_count": 13, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "'b1a3'" ] }, "execution_count": 13, "metadata": {}, "output_type": "execute_result" } ], "source": [ "move.uci()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Thus, this is a move from b1 to a3. \n", "\n", "What piece is this, and where is it moving on the board? Is this a good move?\n", "\n", "The uci string is what each player function will return." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 1.3.2 Standard Algebraic Notation" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "If you know something about Chess, you might know about Standard Algebraic Notation (or san). This is an alternative to uci. You can get a move's san with:" ] }, { "cell_type": "code", "execution_count": 14, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "'Na3'" ] }, "execution_count": 14, "metadata": {}, "output_type": "execute_result" } ], "source": [ "board.san(move)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "However, we will always use uci." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 1.4 Programming a Random Player" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "There is a useful function in the random module that will select from a a list of choices. This is called `random.choice`." ] }, { "cell_type": "code", "execution_count": 15, "metadata": { "collapsed": true }, "outputs": [], "source": [ "import random" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "To use it in a function, we simply:" ] }, { "cell_type": "code", "execution_count": 16, "metadata": { "collapsed": false }, "outputs": [], "source": [ "def random_player(board):\n", " move = random.choice(list(board.legal_moves))\n", " return move.uci()" ] }, { "cell_type": "code", "execution_count": 17, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "'h2h4'" ] }, "execution_count": 17, "metadata": {}, "output_type": "execute_result" } ], "source": [ "random_player(board)" ] }, { "cell_type": "code", "execution_count": 18, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "h2h3\n", "a2a4\n", "g1h3\n", "b2b3\n", "b2b3\n", "e2e4\n", "g1f3\n", "d2d4\n", "c2c4\n", "g1f3\n" ] } ], "source": [ "for i in range(10):\n", " print(random_player(board))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 1.5 Playing a Game" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "To play a game, we'll write a new function called `play_game` that will take two player functions, create a board, and alternatively call the player functions until a win, lose, or draw.\n", "\n", "First, we need some additional modules for displaying a game in the notebook:" ] }, { "cell_type": "code", "execution_count": 19, "metadata": { "collapsed": false }, "outputs": [], "source": [ "import time\n", "from IPython.display import display, HTML, clear_output" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "A useful function for displaying the color of a player:" ] }, { "cell_type": "code", "execution_count": 20, "metadata": { "collapsed": true }, "outputs": [], "source": [ "def who(player):\n", " return \"White\" if player == chess.WHITE else \"Black\"" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "A function for displaying the board as text, or as the nice image (called SVG):" ] }, { "cell_type": "code", "execution_count": 21, "metadata": { "collapsed": true }, "outputs": [], "source": [ "def display_board(board, use_svg):\n", " if use_svg:\n", " return board._repr_svg_()\n", " else:\n", " return \"
\" + str(board) + \"\"\n", " " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "And finally, we can put those together to play a game:" ] }, { "cell_type": "code", "execution_count": 22, "metadata": { "collapsed": false }, "outputs": [], "source": [ "def play_game(player1, player2, visual=\"svg\", pause=0.1):\n", " \"\"\"\n", " playerN1, player2: functions that takes board, return uci move\n", " visual: \"simple\" | \"svg\" | None\n", " \"\"\"\n", " use_svg = (visual == \"svg\")\n", " board = chess.Board()\n", " try:\n", " while not board.is_game_over(claim_draw=True):\n", " if board.turn == chess.WHITE:\n", " uci = player1(board)\n", " else:\n", " uci = player2(board)\n", " name = who(board.turn)\n", " board.push_uci(uci)\n", " board_stop = display_board(board, use_svg)\n", " html = \"Move %s %s, Play '%s':